package com.lcq.study.sort;

/**
 * @ClassName QuickSort
 * @Description
 * @Author lichuanqi
 * @Date 2023/2/22 17:00
 * @Version 1.0
 **/
public class QuickSort {
    // 对数组arr进行快速排序
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        // 调用递归方法，对整个数组进行排序
        quickSort(arr, 0, arr.length - 1);
    }

    // 对数组arr的子区间[left, right]进行快速排序
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        // 选择基准值，这里选择区间的第一个元素
        int pivot = arr[left];
        // 定义两个指针，分别指向左右两端
        int i = left;
        int j = right;
        // 循环交换比基准值小或大的元素
        while (i < j) {
            // 从右向左找到第一个比基准值小的元素
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            // 如果找到了，就交换它和左指针指向的元素
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            // 从左向右找到第一个比基准值大的元素
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            // 如果找到了，就交换它和右指针指向的元素
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        // 循环结束后，左右指针重合，将基准值放到该位置
        arr[i] = pivot;
        // 对左右两个子区间递归进行快速排序
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }

    public static void main(String[] args) {
        int [] a = new int[]{99,88,77,66,55,33,44,11};
        quickSort(a);

        for (int i : a) {
            System.out.println(i);
        }
    }
}
